package cn.corffen.test.algorithm.java;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class DeepSearchJava {

    public int maxAreaOfIsland(int[][] grid) {
        if (grid.length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int answer = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int curArea = 0;
                Deque<Integer> stacki = new LinkedList<>();
                Deque<Integer> stackj = new LinkedList<>();
                stacki.push(i);
                stackj.push(j);
                while (!stacki.isEmpty()) {
                    int curri = stacki.pop();
                    int currj = stackj.pop();
                    if (curri < 0 || currj < 0 || curri == m || currj == n || grid[curri][currj] != 1) {
                        continue;
                    }
                    curArea++;
                    grid[curri][currj] = 0;
                    int[] directionsi = {0, 0, 1, -1};
                    int[] directionsy = {1, -1, 0, 0};

                    //下一步的走向添加到占中
                    for (int k = 0; k < directionsi.length; k++) {
                        int nextI = curri + directionsi[k];
                        int nextJ = currj + directionsy[k];
                        stacki.push(nextI);
                        stackj.push(nextJ);
                    }
                }
                answer = Math.max(answer, curArea);
            }
        }
        return answer;
    }

    public int findCircleNum(int[][] M) {
        int size = M.length;
        int[] visited = new int[size];
        int count = 0;
        for (int i = 0; i < size; i++) {
            if (visited[i] == 0) {
                dfs(M, visited, i);
                count++;
            }
        }
        return count;
    }

    private void dfs(int[][] M, int[] visited, int i) {
        for (int j = 0; j < M.length; j++) {
            if (M[i][j] == 1 && visited[j] == 0) {
                visited[j] = 1;
                dfs(M, visited, j);
            }
        }
    }

    int[] directions = new int[]{-1, 0, 1, 0, -1};

    public List<List<Integer>> pacificAtlantic(int[][] matrix) {
        List<List<Integer>> ans = new ArrayList<>();
        int m = matrix.length;
        if (m == 0 || matrix[0].length == 0) {
            return ans;
        }
        int n = matrix[0].length;
        boolean[][] canReachP = new boolean[m][n];
        boolean[][] canReachA = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            //从左右两边出发
            dfs(matrix, canReachP, i, 0);
            dfs(matrix, canReachA, i, n - 1);
        }

        for (int i = 0; i < n; i++) {
            //从上下两边出发
            dfs(matrix, canReachP, 0, i);
            dfs(matrix, canReachA, m - 1, i);
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (canReachA[i][j] && canReachP[i][j]) {
                    List<Integer> tempList = new ArrayList<>();
                    tempList.add(i);
                    tempList.add(j);
                    ans.add(tempList);
                }
            }
        }
        return ans;
    }

    private void dfs(int[][] matrix, boolean[][] canReach, int i, int j) {
        if (canReach[i][j]) {
            return;
        }
        canReach[i][j] = true;
        int x, y;
        for (int k = 0; k < 4; k++) {
            x = i + directions[k];
            y = j + directions[k + 1];
            if (x >= 0 && x < matrix.length && y >= 0 && y < matrix[0].length && matrix[i][j] <= matrix[x][y]) {
                dfs(matrix, canReach, x, y);
            }
        }
    }

}
